#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0029.py
@time: 2021/11/8 14:32
@desc: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
'''

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root: return
        self.path = []
        def dfs(cur):
            if not cur: return
            # 中序遍历
            dfs(cur.left)
            self.path.append(cur.val)
            dfs(cur.right)
        dfs(root)
        return self.path[-k]

if __name__ == '__main__':
    head = TreeNode(3)
    head.left, head.left.right = TreeNode(1), TreeNode(2)
    head.right = TreeNode(4)
    res = Solution().kthLargest(head, 1)
    print(res)